import java.util.ArrayList;
import java.util.List;

/**
 * 213. 打家劫舍 II
 * https://leetcode-cn.com/problems/house-robber-ii/
 */
public class Solutions_213 {
    public static void main(String[] args) {
        int[] nums1 = {2, 3, 2};  // output: 3
        int[] nums2 = {1, 2, 3, 1};  // output: 4
        int[] nums3 = {0};  // output: 0

        List<int[]> inputs = new ArrayList<>();
        inputs.add(nums1);
        inputs.add(nums2);
        inputs.add(nums3);

        for (int[] input : inputs) {
            int result = rob(input);
            System.out.println(result);
        }
    }

    public static int rob(int[] nums) {
        int len = nums.length;
        if (len == 1) {
            return nums[0];
        } else if (len == 2) {
            return Math.max(nums[0], nums[1]);
        } else if (len == 3) {
            int temp = Math.max(nums[0], nums[1]);
            return Math.max(temp, nums[2]);
        }
        // 在 [0, len - 1) 区间中，得到最优解
        int res1 = dpMethod(nums, 0, len - 1);
        // 在 [1, len) 区间中，得到最优解
        int res2 = dpMethod(nums, 1, len);
        return Math.max(res1, res2);
    }

    public static int dpMethod(int[] nums, int i, int j) {
        // 使用两个变量来记录动态规划的解
        int dp0 = 0, dp1 = 0;
        for (int k = i; k < j; k++) {
            int temp = dp1;
            // 取与不取的比较
            dp1 = Math.max(dp1, dp0 + nums[k]);
            dp0 = temp;
        }
        return dp1;
    }
}
